package sort;

import java.util.Arrays;

public class Sort {

    public static void main(String[] args) {
        Sort sort = new Sort();

        int[] nums1 = new int[]{111, 3, 445, 23, 6, 58, 99, 7};
        sort.bubbleSort(nums1);
        System.out.println(Arrays.toString(nums1));

        int[] nums2 = new int[]{111, 3, 445, 23, 6, 58, 99, 7};
        sort.selectionSort(nums2);
        System.out.println(Arrays.toString(nums2));

        int[] nums3 = new int[]{111, 3, 445, 23, 6, 58, 99, 7};
        sort.insertionSort(nums3);
        System.out.println(Arrays.toString(nums3));

        int[] nums4 = new int[]{111, 3, 445, 23, 6, 58, 99, 7};
        sort.quickSort(nums4);
        System.out.println(Arrays.toString(nums4));

        int[] nums5 = new int[]{111, 3, 445, 23, 6, 58, 99, 7};
        sort.shellSort(nums5);
        System.out.println(Arrays.toString(nums5));

        int[] nums6 = new int[]{111, 3, 445, 23, 6, 58, 99, 7};
        System.out.println(Arrays.toString(sort.mergeSort(nums6)));

        int[] nums7 = new int[]{111, 3, 445, 23, 6, 58, 99, 7};
        sort.heapSort(nums7);
        System.out.println(Arrays.toString(nums7));

        int[] nums8 = new int[]{111, 3, 445, 23, 6, 58, 99, 7};
        int[] nums9 = new int[]{111, 3, 445, 23, 6, 58, 99, 7};
        int[] nums10 = new int[]{111, 3, 445, 23, 6, 58, 99, 7};

    }

    //冒泡排序
    private void bubbleSort(int[] nums) {
        int n = nums.length;
        //n轮交换
        int tmp;
        for (int i = 0; i < n; i++) {
            //交换位置 每轮结束后相对最大的数移动到末尾
            for (int j = 0; j < n - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                }
            }
        }
    }

    //选择排序
    private void selectionSort(int[] nums) {
        int n = nums.length;
        int tmp, minIndex;
        //需要排序的位置
        for (int i = 0; i < n; i++) {
            minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                tmp = nums[i];
                nums[i] = nums[minIndex];
                nums[minIndex] = tmp;
            }
        }
    }

    //插入排序
    private void insertionSort(int[] nums) {
        int n = nums.length, preIndex;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            preIndex = i - 1;
            while (preIndex >= 0 && nums[preIndex] > num) {
                nums[preIndex + 1] = nums[preIndex];
                preIndex--;
            }
            nums[preIndex + 1] = num;
        }
    }

    //快速排序
    private void quickSort(int[] nums) {
        quickSortHelper(nums, 0, nums.length - 1);
    }

    // 1. >=,<=
    // 2. 先右后左
    private void quickSortHelper(int[] nums, int left, int right) {
        if (left > right)
            return;
        int base = nums[left];
        int i = left, j = right;
        while (i != j) {
            //所以最终相遇在最后一个小于基准值的位置
            while (nums[j] >= base && i < j)
                j--;
            while (nums[i] <= base && i < j)
                i++;
            if (i < j)
                swap(nums, i, j);
        }
        swap(nums, left, i);
        quickSortHelper(nums, left, i - 1);
        quickSortHelper(nums, i + 1, right);
    }

    private void quickSortHelper2(int[] nums, int left, int right) {
        if (left > right)
            return;
        int base = nums[left];
        int i = left, j = right;
        while (i != j) {
            //所以最终相遇在大于一个小于基准值的位置
            while (nums[i] <= base && i < j)
                i++;
            while (nums[j] >= base && i < j)
                j--;
            if (i < j)
                swap(nums, i, j);
        }
        swap(nums, right, i);
        quickSortHelper(nums, left, i - 1);
        quickSortHelper(nums, i + 1, right);
    }


    private void quickSortHelper1(int[] nums, int left, int right) {
        if (left > right)
            return;
        //先不考虑递归结束时间
        int i = left;
        int num = nums[i];
        int smallLastIndex = left + 1;
        while (i < right) {
            if (nums[i] < num) {
                swap(nums, i, smallLastIndex);
                smallLastIndex++;
            }
            i++;
        }
        swap(nums, left, smallLastIndex);
        quickSortHelper(nums, left, smallLastIndex - 1);
        quickSortHelper(nums, smallLastIndex + 1, right);
    }

    private void shellSort(int nums[]) {
        //选步长
        for (int step = nums.length / 2; step > 0; step /= 2) {

            for (int i = step; i < nums.length; i++) {
                // i = 当前数 i - step = 前一轮的数
                int value = nums[i];
                int j;
                //倒叙插入
                for (j = i - step; j >= 0 && nums[j] > value; j -= step) {
                    nums[j + step] = nums[j];
                }
                nums[j + step] = value;
            }
        }
    }

    private void shellSort2(int nums[]) {
        //选步长
        for (int step = nums.length / 2; step > 0; step /= 2) {

            for (int i = step; i < nums.length; i++) {
                if (nums[i] < nums[i - step])
                    swap(nums, i, i - step);
            }
        }
    }

    private int[] mergeSort(int nums[]) {
        int length = nums.length;
        if (length < 2)
            return nums;
        int mid = nums.length / 2;
        int[] left = Arrays.copyOfRange(nums, 0, mid);
        int[] right = Arrays.copyOfRange(nums, mid, length);
        return mergeSortHelper(mergeSort(left), mergeSort(right));
    }

    private int[] mergeSortHelper(int left[], int right[]) {
        int leftLength = left.length;
        int rightLength = right.length;
        int[] result = new int[leftLength + rightLength];
        int i = 0, j = 0, index = 0;
        while (i < leftLength && j < rightLength) {
            if (left[i] < right[j]) {
                result[index] = left[i];
                i++;
            } else {
                result[index] = right[j];
                j++;
            }
            index++;
        }
        while (i < leftLength)
            result[index++] = left[i++];
        while (j < rightLength)
            result[index++] = right[j++];
        return result;
    }

    //小顶堆
    private void heapSort(int nums[]) {
        //创建堆
        for (int i = (nums.length - 1) / 2; i >= 0; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            heapSortHelper(nums, i, nums.length);
        }

        for (int i = nums.length - 1; i > 0; i--) {
            int temp = nums[i];
            nums[i] = nums[0];
            nums[0] = temp;
            heapSortHelper(nums, 0, i);
        }
    }

    private void heapSortHelper(int[] arr, int parent, int length) {
        int temp = arr[parent];
        int lChild = 2 * parent + 1;

        while (lChild < length) {
            int rChild = lChild + 1;
            if (rChild < length && arr[lChild] < arr[rChild]) {
                lChild++;
            }
            if (temp >= arr[lChild]) {
                break;
            }
            arr[parent] = arr[lChild];
            parent = lChild;
            lChild = 2 * lChild + 1;
        }
        arr[parent] = temp;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
